#include <stdio.h>
#include <stdlib.h>

/* https://c.biancheng.net/view/3441.html */
void insertSort(int arr[], int temp[], int n) {
    int i, first, final, k;
    //分别记录temp数组中最大值和最小值的位置
    first = final = 0;
    temp[0] = arr[0];
    for(i = 1; i < n; i++) {
        // 待插入元素比最小的元素小
        if(arr[i] < temp[first]) {
            first = (first-1+n) % n;
            temp[first] = arr[i];
        }
        // 待插入元素比最大元素大
        else if(arr[i] > temp[final]) {
            final = (final+1+n) % n;
            temp[final] = arr[i];
        }
        // 插入元素比最小大，比最大小
        else {
            k = (final+1+n) % n;
            //当插入值比当前值小时，需要移动当前值的位置
            while(arr[i] < temp[(k-1+n) % n]) {
                temp[(k+n) % n] = temp[(k-1+n) % n];
                k = (k-1+n) % n;
            }
            //插入该值
            temp[(k+n) % n] = arr[i];
            //因为最大值的位置改变，所以需要实时更新final的位置
            final = (final + 1 + n) % n;
        }
    }
    // 将排序记录复制到原来的顺序表里
    for(k = 0; k < n; k++) {
        arr[k] = temp[(first + k) %n];
    }
}

int main(int argc, char * argv[]) {
    int a[8] = {3, 1, 7, 5, 2, 4, 9, 6};
    int temp[8];
    insertSort(a, temp, 8);
    for(int i = 0; i < 8; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}